package special;

import org.junit.Test;

import java.util.Arrays;

/**
 * @className: LeetCode_31
 * @Description: ...
 * @author: kunkun
 * @date: 2025/3/21 13:49
 */
public class LeetCode_31 {

    @Test
    public void test(){
        int[] nums = new int[]{2,3,1};
        nextPermutation(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+ " ");
        }
    }

    public void nextPermutation(int[] nums) {
        //0. 特殊情况
        if (nums.length == 1 || nums.length==0){
            return;
        }
        //1. 寻找断点
        int index0 = -1,temp = nums[nums.length-1];
        for (int i = nums.length-2; i >=0 ; i--) {
            if (nums[i]>=temp){
                temp = nums[i];
            }else {
                index0 = i;
                break;
            }
        }
        if (index0==-1){
            reverseArray(nums,0, nums.length-1);
            return;
        }
        //2. 寻找比断点大的第一个数
        int index1= -1;
        for (int i = nums.length-1; i >=0 ; i--) {
            if (nums[i]>nums[index0]){
                index1 = i;
                break;
            }
        }
        //3. 交换，反转
        int tempNum = nums[index0];
        nums[index0] = nums[index1];
        nums[index1] = tempNum;
        reverseArray(nums,index0+1,nums.length-1);
    }



    public void reverseArray(int[] nums,int left,int right){
        while (left<=right){
            int temp  = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }



}
